package com.jia.leetCode;

public class Pro0188 {
    public int maxProfit(int frequence, int[] prices) {
        if (prices == null || prices.length == 0 || frequence < 1) {
            return 0;
        }
        //当次数frequence大于prices长度，转化pro122做法
        if(frequence >= prices.length) {
            return  maxProfit(prices);
        }
        //同pro188做法
        int[][][] dp = new int[prices.length][2][frequence+1]; //2中，0表示没持有和1持有股票，frequence表示交易的笔数
        //初始化
        for(int i = 0; i <= frequence; i++) {
            dp[0][1][i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k <= frequence; k++) {
                    if(k == 0 && j == 0) continue;
                    if(j == 1) {
                        dp[i][1][k] = Math.max(dp[i-1][0][k] - prices[i], dp[i-1][1][k]);
                    }else {
                        dp[i][0][k] = Math.max(dp[i-1][1][k-1] + prices[i], dp[i-1][0][k]);
                    }
                }
            }
        }
        int maxProfit = 0;
        for(int i = 1; i <= frequence; i++) {
            maxProfit = Math.max(dp[prices.length - 1][0][i], maxProfit);
        }
        return maxProfit;
    }
    public int maxProfit(int[] prices) {
        if(prices.length < 2) return 0;
        int result = 0;
        for(int i=1; i<prices.length; i++) {
            if(prices[i-1] < prices[i])
                result += (prices[i] - prices[i-1]);
        }
        return result;
    }

    public static void main(String[] args) {
        Pro0188 pro0188 = new Pro0188();
        System.out.println(pro0188.maxProfit(1, new int[]{1,2}));;
    }
}
